package LC;

/**
 * https://leetcode.com/problems/rotate-list/description/
 * Given a list, rotate the list to the right by k places,
 * where k is non-negative.
 * For example:
 * Given 1->2->3->4->5->NULL and k = 2,
 * return 4->5->1->2->3->NULL.
 */
public class LC_061_RotateList_LinkedList_Loop {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        int k = 2;
        ListNode newList = Solution.rotateRight(head, k);
        printList(newList);
    }

    private static void printList(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    static class Solution {
        static ListNode rotateRight(ListNode head, int k) {
            if (head == null || k <= 0)
                return head;

            // 新建一个结点，利于操作
            ListNode tmpHead = new ListNode(0);
            tmpHead.next = head;
            // 使用快慢指针，计算倒数节点数目
            ListNode fast = tmpHead;
            ListNode slow = tmpHead;
            int len = 0;
            // 计算链表长度
            while (slow.next != null) {
                len++;
                slow = slow.next;
            }
            slow = tmpHead;
            // 关键，记录k 的有效长度，输入会有k大于链表长度值
            k = (len + (k % len)) % len;
            // 不需要翻转
            if (k == 0)
                return tmpHead.next;
            // 快指针先走k步
            while (--k >= 0)
                fast = fast.next;
            // 一起走
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            // 重新链接链表，注意置空
            tmpHead.next = slow.next;
            fast.next = head;
            slow.next = null;
            return tmpHead.next;
        }
    }
}
